1. Technical Field
The present invention relates to the technical field of graphic rendering and, in particular, to a rasterizing method for finding and rendering all the pixels of the screen associated with a primitive.
2. Description of the Related Art
A virtual three dimensional (3D) model (or simply “3D model”) is comprised of primitives in the form of polygons, such as triangles, which represent the skin of the 3D model. A graphic 3D engine draws polygons from the 3D model onto a two-dimensional (2D) surface, such as a screen.
A summary of the prior art rendering process can be found in: “Fundamentals of Three-Dimensional Computer Graphics”, by Watt, Chapter 5: The Rendering Process, pages 97 to 113, published by Addison-Wesley Publishing Company, Reading, Mass., 1989, reprinted 1991, ISBN 0-201-15442-0.
In a traditional pipeline, the primitives are processed in a submission order. A more efficient method is to break up the frame buffer into individual subsections (tiles) and to render them individually. Each tile includes one or more polygons or, more typically, a portion of one or more polygons.
A tile based rendering employs therefore a way to associate tiles covered by a primitive. A rasterizer renders all primitives of one tile, so which tile is covered by that primitive is found first.
To reduce the amount of tiles that each polygon is assigned to, a primitive or polygon binning method may be used. A polygon binning method excludes tiles that do not include any polygons or portions thereof prior to rasterization. The binning process also accomplishes some rasterization setup by identifying which polygons are contained by each tile.
The rasterizing process comprises receiving the vertices of a primitive, finding all the pixels associated with the primitive, and rendering all the pixels. Rendering implies associating with each pixel a set of attributes. The attributes are data (color, coordinates position, texture coordinate etc.) associated with a primitive. Starting from the attributes of the vertices of a primitive, the rasterizer finds the attributes of each pixel by interpolation.
Some kinds of rasterizers are already known.
One of the most used rasterizers is known as Bresenham. Starting from a triangle vertex, it uses an incremental technique which finds border pixels using the Bresenham scan line.
Another approach is known as RLI. Also this method always starts from a triangle vertex and uses another scan line technique to find border pixels.
This is an incremental technique that reduces the possibility to have a high parallelism. It calculates all attributes using deltax, deltay, deltaz coordinates of the current pixels. The calculation attribute is incremental, so it saves a lot of operations compared to the Bresenham. However, the rendering direction is not flexible.
A further approach is known as Homogeneus, because all calculations are performed into homogeneous space (defined by x, y, z, w coordinates). It does not use a scan line technique to find border pixels but it makes a test location based on an edge equation. It can start from any point for rendering, and it can calculate all attributes using deltax, deltay, deltaz coordinates of the current pixel. However, since all calculations are made into homogeneous space, this technique requires more computation then RLI.
There is therefore the need of rendering pixels in a more efficient way, in order to reduce the amount of processing to be performed by the 3D graphic engine.